/*
Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.
*/

class Solution {
public:
    int totalNQueens(int n) {
        int total = 0;
        if (n) {
            vector<int> board(n,0);
            placeQueen(0, board, total);
        }
        return total;
    }
private:
    void placeQueen(int row, vector<int> &board, int &total) {
        if (row == board.size()) {
            total++;  // complete answer
        } else {
            // try to place queen on each column    
            for (int col=0; col<board.size(); col++) {
                if (checkValid(row, col, board)) {
                    board[row] = col;   // place queen
                    placeQueen(row+1, board, total);
                }
             }
        }
    }
    bool checkValid(int row, int col, vector<int> &board) {
        for (int i=0; i < row; i++) {
            if (col == board[i]) return false;                // check column
            if ((row-i) == abs(col-board[i])) return false;   // check diagonal
        }
        return true;
    }
};
